package com.fan.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 马踏棋盘算法，骑士周游算法
 *
 * @author 19252
 * @date 2020/8/10
 */
public class HorseChessBoard {

    /**
     * 棋盘的行数
     */
    private static int rows;

    /**
     * 棋盘的列数
     */
    private static int cols;

    /**
     * 二维换一维
     * 处在第几行第几列，每列有多少个数，就可以完成转换
     * 记录棋盘上的每个位置是否被访问过
     */
    private static boolean[] isVisited;

    /**
     * 标记是否完成遍历
     */
    private static boolean isFinished;


    public static void main(String[] args) {
        // 算法测试
        rows = 8;
        cols = 8;
        int[][] chessBoard = new int[rows][cols];
        isVisited = new boolean[rows * cols];
        Arrays.fill(isVisited, false);
        int row = 0;
        int col = 0;
        int step = 1;
        long startTime = System.currentTimeMillis();
        traversalChessBoard(chessBoard, row, col, step);
        System.out.println("start");
        long endTime = System.currentTimeMillis();
        System.out.println("花费时间：" + (endTime - startTime) + " ms");
        System.out.println("end");
        for (int[] rows : chessBoard){
            System.out.println(Arrays.toString(rows));
        }
    }

    /**
     * 遍历棋盘算法
     * @param chessBoard 棋盘 （二维数组）
     * @param row 遍历行起点
     * @param col 遍历列起点
     * @param step 遍历到第几步
     */
    public static void traversalChessBoard(int[][] chessBoard, int row, int col, int step){
        chessBoard[row][col] = step;
        // 在进入该点时无论该点能否完成遍历都先置为被访问
        isVisited[row * cols + col] = true;
        ArrayList<Point> points = next(new Point(col, row));
        sort(points);
        // 遍历集合获取当前点可以前往的下一个坐标点
        Point point;
        while(!points.isEmpty()){
            // 取出下一个点
            point = points.remove(0);
            // 判断该点是否被访问过
            if (!isVisited[point.y * rows + point.x]){
                // 没有被访问过，递归遍历
                traversalChessBoard(chessBoard, point.y, point.x, step + 1);
            }
        }

        // 判断棋盘的遍历是否完成
        // step < rows * cols 的两种情况
        // 1: 棋盘到目前位置还为走完
        // 2: 棋盘处于回溯状态
        if (step < rows * cols && !isFinished){
            // 没完成，将当前位置置为 0
            chessBoard[row][col] = 0;
            // 并且变为 还为遍历
            isVisited[row * rows + col] = false;
        }else {
            // 完成遍历
            isFinished = true;
        }
    }

    /**
     * 贪心算法的思想
     * 根据当前位置的
     * 每一个可遍历的位置[ArrayList<Point> points]
     * 的可遍历位置个数[next(o1).size()]进行非递减排序
     * （用来减少遍历回溯次数）
     */
    public static void sort(ArrayList<Point> points){
        points.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return next(o1).size() - next(o2).size();
            }
        });
    }


    /**
     * 根据当前位置（Point 对象），计算马儿还能走哪些位置（Point），并放入一个集合中（ArrayList<Point>），最多有八个位置
     *
     * @param currentPoint 当前马儿所在的位置
     * @return 马儿可以走的位置
     */
    public static ArrayList<Point> next(Point currentPoint) {
        // 创建保存位置的集合
        ArrayList<Point> points = new ArrayList<>();
        // 创建一个point (Point 在这里表达为是坐标系上的点，x 为列， y 为 行)
        Point p1 = new Point();
        // 二维数组存储，坐标原点(0, 0) 在左上角
        //表示马儿可以走5这个位置
        if ((p1.x = currentPoint.x - 2) >= 0 && (p1.y = currentPoint.y - 1) >= 0) {
            points.add(new Point(p1));
        }
        //判断马儿可以走6这个位置
        if ((p1.x = currentPoint.x - 1) >= 0 && (p1.y = currentPoint.y - 2) >= 0) {
            points.add(new Point(p1));
        }
        //判断马儿可以走7这个位置
        if ((p1.x = currentPoint.x + 1) < rows && (p1.y = currentPoint.y - 2) >= 0) {
            points.add(new Point(p1));
        }
        //判断马儿可以走0这个位置
        if ((p1.x = currentPoint.x + 2) < rows && (p1.y = currentPoint.y - 1) >= 0) {
            points.add(new Point(p1));
        }
        //判断马儿可以走1这个位置
        if ((p1.x = currentPoint.x + 2) < rows && (p1.y = currentPoint.y + 1) < cols) {
            points.add(new Point(p1));
        }
        //判断马儿可以走2这个位置
        if ((p1.x = currentPoint.x + 1) < rows && (p1.y = currentPoint.y + 2) < cols) {
            points.add(new Point(p1));
        }
        //判断马儿可以走3这个位置
        if ((p1.x = currentPoint.x - 1) >= 0 && (p1.y = currentPoint.y + 2) < cols) {
            points.add(new Point(p1));
        }
        //判断马儿可以走4这个位置
        if ((p1.x = currentPoint.x - 2) >= 0 && (p1.y = currentPoint.y + 1) < cols) {
            points.add(new Point(p1));
        }
        return points;
    }
}
